package ztttt1;

import java.util.*;

public class ListNodetest extends MyList {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);


    }
    //203.移除链表元素

    class Solution {
        public ListNode removeElements(ListNode head, int val) {
            if (head == null) {
                return head;
            }
            ListNode cur = head.next;
            ListNode cur0 = head;
            while (cur != null) {
                if (cur.val == val) {
                    cur0.next = cur.next;
                } else {
                    cur0 = cur;
                }
                cur = cur.next;
            }
            if (cur.val == val) {
                cur0.next = cur.next;
            }
            return head;
        }
    }

    //206.反转链表

    class Solution1 {
        public ListNode reverseList(ListNode head) {
            if (head == null) {
                return null;
            }
            ListNode cur = head.next;
            head.next = null;
            while (cur != null) {
                ListNode curNext = cur.next;
                cur.next = head;
                head = cur;
                cur = cur.next;
            }
            return head;
        }
    }

    //876.链表中间结点

    class Solution2 {
        public ListNode middleNode(ListNode head) {
            if (head == null) {
                return null;
            }
            ListNode slow = head;
            ListNode fast = head;
            while (fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            return slow;
        }
    }

    //面试题 链表倒数第k个

    class Solution3 {
        public int kthToLast(ListNode head, int k) {
            ListNode cur1 = head;
            ListNode cur2 = head;
            for (int i = 0; i < k - 1; i++) {
                cur1 = cur1.next;
            }
            while (cur1.next != null) {
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
            return cur2.val;
        }
    }

    //21.合并两个有序列表

    //初版:
    class Solution4 {
        public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
            ListNode list = new ListNode();
            list = list.next;
            if(list1 == null){
                return list2;
            }
            if(list2 == null){
                return list1;
            }
            while(list1 != null && list2 != null){
                if(list1.val > list2.val){
                    list = addLast(list, list2.val);
                    list2 = list2.next;
                }else if(list1.val <= list2.val){
                    list = addLast(list, list1.val);
                    list1 = list1.next;
                }
            }
            if(list1 == null){
                while(list2 != null){
                    list = addLast(list, list2.val);
                    list2 = list2.next;
                }
            }else if(list2 == null){
                while(list1 != null){
                    list = addLast(list, list1.val);
                    list1 = list1.next;
                }
            }
            return list;
        }
        public ListNode addLast(ListNode list,int val){
            ListNode node = list;
            ListNode cur = new ListNode(val);
            if(list == null){
                return cur;
            }
            while(node.next != null){
                node = node.next;
            }
            node.next = cur;
            return list;
        }
    }
    //第二版:
    class Solution5 {
        public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
            if(list1 == null){
                return list2;
            }
            if(list2 == null){
                return list1;
            }
            ListNode node = new ListNode();
            ListNode list = node;
            while(list1 != null && list2 != null){
                if(list1.val > list2.val){
                    list.next = list2;
                    list2 = list2.next;
                }else if(list1.val <= list2.val){
                    list.next = list1;
                    list1 = list1.next;
                }
                list = list.next;
            }
            if(list1 == null){
                list.next = list2;
            }if(list2 == null){
                list.next = list1;
            }
            return node.next;
        }
    }
}










